Red-Black Tree

Red-Black Tree 是一種自平衡二叉搜索樹，用於數據結構中的排序和檢索操作。它於樹中節點的顏色標記，以確保樹的平衡性。

在紅黑樹中，每個節點都被標記為紅色或黑色，並且滿足以下紅黑樹的性質：

1. 每個節點都是紅色或黑色。
2. 根節點是黑色。
3. 每個葉子節點（NIL節點，通常表示為黑色）都被視為黑色。
4. 如果一個節點是紅色，則其兩個子節點都是黑色。
5. 任意一條從根節點到葉子節點的路徑上，不能有兩個連續的紅色節點。
6. 任意一條從根節點到葉子節點的路徑上，黑色節點的數量必須相等。

紅黑樹的自平衡性質確保了在插入或刪除操作後，樹的高度保持相對平衡，從而保持了搜索、插入和刪除操作的平均時間複雜度為，其中是樹中節點的數量。

紅黑樹實現平衡搜索數據結構時，如數據庫索引、自平衡映射和集合。

它的自平衡性和高效性使其成為一個重要的數據結構，用於儲存和檢索大量數據。

package rbtree

import java.util.LinkedList
import java.util.IdentityHashMap

enum class Color {
    BLACK,
    RED
}

class Node<T : Comparable<T>>(val value: T,
                              var color: Color = Color.BLACK) : Comparable<Node<T>> {
    var left: Node<T>? = null
    var right: Node<T>? = null
    var parent: Node<T>? = null
    val isRoot: Boolean
        get() = this.parent == null

    override fun toString(): String {
        val right = right.toStringEvenIfNull()
        val left = left.toStringEvenIfNull()
        val parent = parent.toStringEvenIfNull()
        val main = toStringEvenIfNull()
        return "$main.${if (!isRoot) " Parent: $parent." else ""} Left: $left. Right: $right."
    }

    override operator fun compareTo(other: Node<T>): Int = value.compareTo(other.value)

    fun T.compareTo(): Int = value.compareTo(this)

    fun addLeftNode(node: Node<T>) {
        left = node
        node.parent = this
    }

    fun addRightNode(node: Node<T>) {
        right = node
        node.parent = this
    }

    fun addChildNode(node: Node<T>) {
        if (node < this) {
            addLeftNode(node)
            return
        }
        addRightNode(node)
    }

    fun isLeftChild() = this === this.parent?.left
    fun isRightChild() = this === this.parent?.right

    fun uncle(): Node<T>? {
        if (isLeftChild()) return parent?.right
        if (isRightChild()) return parent?.left
        return null
    }

    fun leftRotate() {
        val child = right!!
        val childLeft = child.left
        right = childLeft
        if (childLeft !== null) childLeft.parent = this
        if (isLeftChild()) parent?.left = child
        if (isRightChild()) parent?.right = child
        child.parent = parent
        child.left = this
        parent = child
    }

    fun rightRotate() {
        val child = left!!
        val childRight = child.right
        left = childRight
        if (childRight !== null) childRight.parent = this
        if (isLeftChild()) parent?.left = child
        if (isRightChild()) parent?.right = child
        child.parent = parent
        child.right = this
        parent = child
    }
}

fun <T : Comparable<T>> Node<T>?.toStringEvenIfNull(): String {
    if (this == null) return "Leaf"
    val prefix = if (color == Color.BLACK) "B" else "R"
    val nodeName = if (isRoot) "Root" else "Node"
    return "${prefix}${nodeName}($value)"
}

class Tree<T : Comparable<T>>(val rootValue: T) {
    var root = Node<T>(rootValue)

    fun breadthFirstTraversal(function: (T?) -> Unit) {
        val dequeue = LinkedList<Node<T>?>(listOf(root))
        while (dequeue.isNotEmpty()) {
            val el = dequeue.poll()
            function(el?.value)
            if (el !== null) {
                dequeue.add(el.left)
                dequeue.add(el.right)
            }
        }
    }

    fun breadthFirstNodeTraversal(function: (Node<T>?) -> Unit) {
        val dequeue = LinkedList<Node<T>?>(listOf(root))
        while (dequeue.isNotEmpty()) {
            val el = dequeue.poll()
            function(el)
            if (el !== null) {
                dequeue.add(el.left)
                dequeue.add(el.right)
            }
        }
    }

    fun isValidRedBlackTree(): Pair<Boolean, String> {
        if (root.color == Color.RED) {
            return Pair(false, "Root node should be black.")
        }

        var msg = ""
        breadthFirstNodeTraversal {
            if (msg != "") return@breadthFirstNodeTraversal
            if (it !== null && it.color == Color.RED) {
                val left = it.left
                if (left !== null && left.color == Color.RED) {
                    msg = "2 red children: $it"
                    return@breadthFirstNodeTraversal
                }
                val right = it.right
                if (right !== null && right.color == Color.RED) {
                    msg = "2 red children: $it"
                    return@breadthFirstNodeTraversal
                }
            }
        }
        if (msg != "") return Pair(false, msg)

        var sameLeafBlackHeight : Long = -1
        val blackHeightMap = IdentityHashMap<Node<T>?, Long>()
        blackHeightMap[null] = 0
        breadthFirstNodeTraversal {
            if (msg != "") return@breadthFirstNodeTraversal
            if (it === null) return@breadthFirstNodeTraversal
            val increment = if (it.color == Color.BLACK) 1 else 0
            val blackHeight = blackHeightMap[it.parent]!! + increment
            blackHeightMap[it] = blackHeight

            if ((it.left === null) && (it.right == null)) {
                if (sameLeafBlackHeight == -1.toLong()) {
                    sameLeafBlackHeight = blackHeight
                } else if (sameLeafBlackHeight != blackHeight) {
                    msg = "Expected black height: $sameLeafBlackHeight. Actual: $blackHeight. Node: $it"
                }
            }
        }
        if (msg != "") return Pair(false, msg)

        return Pair(true, "")
    }

    override fun toString(): String {
        val sb = StringBuilder()
        breadthFirstTraversal {
            sb.append(it.toString())
            sb.append(' ')
        }
        return sb.trim().toString()
    }

    fun unbalancedInsert(value: T) : Node<T> {
        var curNode: Node<T>? = this.root
        var curParent: Node<T> = this.root
        while (curNode != null) {
            curParent = curNode
            curNode = if (value < curNode.value) curNode.left else curNode.right
        }
        val newNode = Node(value, color = Color.RED)
        curParent.addChildNode(newNode)
        return newNode
    }

    fun redBlackInsertFixup(newNode: Node<T>) {
        var nodeInserted = newNode
        // newNode must have a parent as it is not root
        var parent = nodeInserted.parent!!
        while (parent.color == Color.RED) {
            val uncle = parent.uncle()
            if (uncle?.color == Color.RED) {
                parent.color = Color.BLACK
                uncle.color = Color.BLACK

                // because the tree is invalid Red-Black tree it means
                // that there are 2 red nodes, thus the parent must have a parent
                nodeInserted = parent.parent!!
                nodeInserted.color = Color.RED
                if (nodeInserted === root) {
                    break
                }
                parent = nodeInserted.parent!!
                continue
            }

            if (parent.isLeftChild()) {
                if (nodeInserted.isRightChild()) {
                    nodeInserted = nodeInserted.parent!! // not root as it is red
                    nodeInserted.leftRotate()
                    parent = nodeInserted.parent!!
                }

                parent.color = Color.BLACK
                parent.parent!!.color = Color.RED
                val toRightRotate = parent.parent!!
                if (toRightRotate == root) {
                    root = toRightRotate.left!!
                }
                toRightRotate.rightRotate()
            } else if (parent.isRightChild()) {
                if (nodeInserted.isLeftChild()) {
                    nodeInserted = nodeInserted.parent!! // not root as it is red
                    nodeInserted.rightRotate()
                    parent = nodeInserted.parent!!
                }

                parent.color = Color.BLACK
                parent.parent!!.color = Color.RED
                val toLeftRotate = parent.parent!!
                if (toLeftRotate == root) {
                    root = toLeftRotate.right!!
                }
                toLeftRotate.leftRotate()
            } else {
                throw RuntimeException("Should be unreachable by the algorithm.")
            }
        }

        root.color = Color.BLACK
    }

    fun balancedInsert(value: T) : Node<T> {
        val node = unbalancedInsert(value)
        redBlackInsertFixup(node)
        return node
    }
}


fun main(args: Array<String>) {
    val tree = Tree<Long>(3)
    tree.unbalancedInsert(10)
    tree.unbalancedInsert(2)
    tree.unbalancedInsert(12)
    println(tree.root)
    println(tree.root.right)
}

所有 Code 可以在 Github 找到 ～

明天進入到 Graph 的環節！

Reference

• kotlin-algos